package com.practice.shua1;

import java.util.LinkedList;

/**
 * 【题目】：（TODO：滑动窗口+窗口内最大值的更新结构+窗口内最小值的更新结构）
 * 给定一个整型数组arr，和一个正数num。某个arr中的子数组sub，如果想达标，
 * 必须满足：sub中最大值-sub中最小值 <= num，返回arr中达标子数组的数量。
 *
 * @author lineng
 * @create 2021-05-03 11:09
 */
public class Code_05_AllLessNumSubArray {

    // 如果 arr[l....r] 满足要求，说明 max-min<=num
    // 当窗口变小时，max可能变小或者不变，min可能变大或者不变，
    // 那么一定有 newMax - newMin <= num
    // 说明达标的窗口，缩小后依然达标

    // 如果 arr[l...r] 不满足要求，说明 max-min > num
    // 当窗口变大时，max可能变大或者不变，min可能变小或者不变，
    // 那么一定有 newMax-newMin > num
    // 说明不达标的窗口扩大后一定不达标

    // 我们规定下 [L...R)表示窗口，[0...0)表示窗口一个数也没有，[0...1)表示窗口只有arr[0]这个数

    public static int myAnswerOpt(int[] arr, int num) {

        if (arr == null || arr.length == 0) {
            return 0;
        }
        int res = 0;
        LinkedList<Integer> maxQueue = new LinkedList<>();
        LinkedList<Integer> mixQueue = new LinkedList<>();
        int L = 0;
        int R = 0;
        while (L < arr.length) {
            int max = 0;
            int mix = 0;
            if (!maxQueue.isEmpty()) {
                max = arr[maxQueue.peekFirst()];
            }
            if (!mixQueue.isEmpty()) {
                mix = arr[mixQueue.peekFirst()];
            }
            while (R < arr.length) {
                while (!maxQueue.isEmpty() && arr[maxQueue.peekLast()] <= arr[R]) {
                    maxQueue.pollLast();
                }
                maxQueue.addLast(R);

                while (!mixQueue.isEmpty() && arr[mixQueue.peekLast()] >= arr[R]) {
                    mixQueue.pollLast();
                }
                mixQueue.add(R);
                if (!maxQueue.isEmpty()) {
                    max = arr[maxQueue.peekFirst()];
                }
                if (!mixQueue.isEmpty()) {
                    mix = arr[mixQueue.peekFirst()];
                }
                if (max - mix > num){
                    break;
                }
                R++;
            }
            res += R - L;

            if (!maxQueue.isEmpty() && L == maxQueue.peekFirst()) {
                maxQueue.pollFirst();
            }
            if (!mixQueue.isEmpty() && L == mixQueue.peekFirst()) {
                mixQueue.pollFirst();
            }

            // L失效
            L++;

        }
        return res;
    }


    // 我的解法（当前解法不是最优解，当前解法的时间复杂度为O(n^2)）
    public static int myAnwser(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int res = 0;
        LinkedList<Integer> maxQueue = new LinkedList<>();
        LinkedList<Integer> mixQueue = new LinkedList<>();
        for (int L = 0; L < arr.length; L++) {
            int curMaxNum = 0;
            int curMixNum = 0;
            for (int R = L; R < arr.length; R++) {
                while (!maxQueue.isEmpty() && arr[maxQueue.peekLast()] <= arr[R]) {
                    maxQueue.pollLast();
                }
                maxQueue.addLast(R);
                while (!mixQueue.isEmpty() && arr[mixQueue.peekLast()] >= arr[R]) {
                    mixQueue.pollLast();
                }
                mixQueue.addLast(R);

                if (!maxQueue.isEmpty()) {
                    curMaxNum = arr[maxQueue.peekFirst()];
                }
                if (!mixQueue.isEmpty()) {
                    curMixNum = arr[mixQueue.peekFirst()];
                }
                if ((curMaxNum - curMixNum) <= num) {
                    res++;
                }
            }
            maxQueue.clear();
            mixQueue.clear();
        }
        return res;
    }

    // 左神解法：TODO：作为对数器
    public static int getNum(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        LinkedList<Integer> qmin = new LinkedList<Integer>();
        LinkedList<Integer> qmax = new LinkedList<Integer>();
        int L = 0;
        int R = 0;
        // [L..R) -> [0,0) 窗口内无数 [1,1)
        // [0,1) -> [0~0]
        int res = 0;
        while (L < arr.length) { // L是开头位置，尝试每一个开头

            // 如果此时窗口的开头是L,下面的while工作:R向右扩到违规为止

            while (R < arr.length) { // R是最后一个达标位置的再下一个
                while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[R]) {
                    qmin.pollLast();
                }
                qmin.addLast(R);
                // R -> arr[R],
                while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
                    qmax.pollLast();
                }
                qmax.addLast(R);

                if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) {
                    break;
                }
                R++;
            }

            // R是最后一个达标位置的再下一个，第一个违规的位置
            res += R - L;

            if (qmin.peekFirst() == L) {
                qmin.pollFirst();
            }
            if (qmax.peekFirst() == L) {
                qmax.pollFirst();
            }

            L++;

        }
        return res;
    }

    // for test
    public static int[] getRandomArray(int len) {
        if (len < 0) {
            return null;
        }
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = (int) (Math.random() * 10);
        }
        return arr;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr != null) {
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[] arr = getRandomArray(30);
        int num = 5;
        printArray(arr);
        System.out.println(getNum(arr, num));
        System.out.println("=======================");
        int myAnwser = myAnwser(arr, num);
        System.out.println(myAnwser);
        System.out.println("***********************");
        int myAnswerOpt = myAnswerOpt(arr, num);
        System.out.println(myAnswerOpt);
    }
}
